Batch 2 - Class 48 - Graphs I

• In the problem above, what is the smallest number of squares that can be colored green, so that every tromino has at least one green square?

  Answer: 32 again! (in above 2x2 squares, with anything less than 32 greens, there will be a square with 0 or 1 green, hence a non-green tromino)

• MC Chap 5 - Problem 1 - Cosmic liaisons are formed among the nine planets of the solar system. Rockets travel along the following routes: Earth-Mercury, Pluto-Venus, Earth-Pluto, Pluto-Mercury, Mercury-Venus, Uranus-Neptune, Neptune-Saturn, Saturn-Jupiter, Jupiter-Mars, and Mars-Uranus. Can a traveler get from Earth to Mars?

  Answer: No. If one draws a graph with planets as vertices, and paths as edges, then one can see that there is no path from Earth to Mars

• MC Chap 5 - Problem 2 - Look at the two figures (starting point and destination point). Several knights are situated on a 3x3 chessboard as shown in Starting Point. Can they move, using the usual chess knight's move, to the position shown in Destination Point? 

• Answer: No. If one draws a graph of all possible paths by labeling each square of the 3x3 chessboard, then knights need to go from first to second position below. For this, the white and black knights would need to cross over, i.e. be on the same square simultaneously, which is not allowed

• MC Chap 5 - Problem 3 - A chessboard has the form of a cross shown below. Can a knight travel around this board passing each square exactly once, and end on the square it started on?

• Answer: Yes. Like in previous problem, one can draw a graph of all moves. The knight can now simply walk around the circle.

• Sum of degrees of all vertices is even 
• Sum of degrees of all vertices is twice the number of edges - explain why
• Even sum implies that there have to be even number of odd-degree vertices

• MC Chap 5 - Problem 10 - A king has 19 vassals. Can it happen that each vassal has either 1, 5 or 9 neighbours

  Answer: No. This would imply an odd number (19) of vertices, each with odd degree

• MartinShCol - 1.18 - My wife and I recently attended a party at which there were four other couples. Various handshakes took place. No one shook hands with himself/herself or with his/her spouse, and no one shook hands with the same person twice. After all handshakes were over, I asked each person, including my wife, how many hands he/she had shaken. They all gave me a different answer. How many hands did I shake?

  Hint: Instead of 5 couples, solve for 2 couples, then for 3 and so on. See the pattern